package leecode;

import java.util.Arrays;

/**
 * @author: lwg
 * @Date: 2021/5/4 17:20
 * @Description: 利用快速选择来得到前k个最小数字  整个排序后选择前k个
 */
public class QuickSelect {
    public static int[] getLeastNumbers(int[] arr, int k) {
        quickSort(arr, 0, arr.length - 1);
        return Arrays.copyOf(arr, k);
    }

    private static void quickSort(int[] arr, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) {
            return;
        }
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i = l, j = r;
        //当i==j跳出循环
        while (i < j) {
            //下面的i<j避免j--的时候超出索引
            while (i < j && arr[j] >= arr[l]) {
                j--;
            }
            while (i < j && arr[i] <= arr[l]) {
                i++;
            }
            swap(arr, i, j);
        }
        //将基准数与中间的值进行交换
        swap(arr, i, l);
        // 递归左（右）子数组执行哨兵划分
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] array = new int[]{5, 4, 6, 3, 4, 8};
        System.out.println(Arrays.toString(getLeastNumbers(array, 4)));
    }

}
